//1.二分+抽屉原理。抽屉原理： 在 [1,𝑚] 只有 𝑚 个可能值，若出现 𝐶(𝑚)>𝑚，则至少一个值在该子集重复，且该值不大于 𝑚。
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int _size = nums.size();
        int left = 1;
        int right = _size - 1;
        int count;
        while(left < right) {
            int mid = (left+right)/2;
            count=0;
            //如果没有重复数，理论上 ≤ mid 的元素最多有 mid 个。
            //如果 count > mid，说明在 [1, mid] 这个范围里已经“塞”进了超过 mid 个数，必然有重复数落在这个区间。
            for(int i=0; i< _size; ++i) {
                if(nums[i] <= mid)
                    count++;
            }
            if(count > mid) {
                right = mid;    // 重复数在 [left, mid]
            }
            else
                left = mid+1;   // 重复数在 [mid+1, right]
        }

        return left;
    }
};

//2.Floyd 判圈算法（快慢指针）--时间 O(n)-----一旦把数组看作链表，就能直接套用 Floyd 判圈算法（快慢指针）。

/*
1. 数组和链表的“映射关系”
在数组 nums 里，每个元素的值都在 [1, n] 范围内。
我们可以把 下标 i 当作链表的节点，而它的“next 指针”就是 nums[i]。

例如：如果 nums[3] = 5，就画一条边 3 → 5。

这样，整个数组就变成了一张“函数图”：每个节点都有且只有一条出边。

2. 为什么一定会形成环
数组长度是 n+1，但值域只有 n。

这意味着至少有两个不同的下标指向同一个值（也就是重复数）。

在“链表视角”下，这就等价于：某个节点有两个前驱指向它。

结果就是：从起点（下标 0）出发，沿着 i → nums[i] 一直走，最终一定会进入一个环。

3. 环入口为什么就是重复数
假设重复的数是 d，那么至少有两个不同的下标 p 和 q 满足 nums[p] = nums[q] = d。

在链表图里，节点 d 就有两条边指向它：一条来自 p，一条来自 q。

这就导致了“尾巴部分”最终接入环的入口节点是 d。

所以环的入口节点就是重复数。
*/
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int fast = 0;
        int slow = 0;
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while(slow != fast) ;
        slow = 0;
        while(slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
};

/*
唯一重复的值 d：数组长度为 n+1，但值域只有 n。题目还假定只有一个重复值 d，这意味着恰好有两个不同的下标 p ≠ q 满足 nums[p] = nums[q] = d。

一个具体例子把路径走一遍：
数组：nums = [1,3,4,2,2]，下标 0..4，值域 1..4
路径：

0 → nums[0]=1

1 → nums[1]=3

3 → nums[3]=2

2 → nums[2]=4

4 → nums[4]=2

2 → 4 → 2 → 4 → …

结构：尾巴是 0→1→3，入口是 2，环是 2→4→2。重复值是 2（因为 nums[3]=2 和 nums[4]=2），入口也正是 2。
*/





